/**
 * Created with IntelliJ IDEA
 * Description:
 * User:恋恋
 * Date:2022-10-05
 * Time:9:05
 */
public class MySingleLink {
    //静态内部类
    static class LinkedList{
        int val;
        LinkedList next;
        public LinkedList(int val) {
            this.val = val;
        }
    }
    LinkedList head;
    //头插法
    public void addFirst(int data){
        if(this.head==null){
            head=new LinkedList(data);
        }else{
            LinkedList linkedList=new LinkedList(data);
            linkedList.next=this.head;
            this.head=linkedList;
        }
    }
    public void display(MySingleLink mySingleLink){
        LinkedList linkedList=this.head;
        while(linkedList!=null){
            System.out.print(linkedList.val+" ");
            linkedList=linkedList.next;
        }
    }
    public boolean palindrome(LinkedList head){
        //首先找到链表的中间节点
        LinkedList fast=head;
        LinkedList slow=head;
        LinkedList cur;
        LinkedList curNext;
        //为空链表
        if(head==null){
            return false;
        }
        //只有一个结点
        if(head.next==null){
            return true;
        }
        //偶数个或者ji数个
        while(fast!=null&&fast.next!=null){
            fast=fast.next.next;
            slow=slow.next;
        }
        //此时的中间节点是slow
        //然后翻转中间节点后面的链表
        cur=slow.next;
        while(cur!=null){
            curNext=cur.next;
            cur.next=slow;
            slow=cur;
            cur=curNext;
        }
        //此时的slow是逆置的头节点
        while(head!=slow){
            if(head.val!=slow.val){
                return false;
            }
            //处理偶数情况
            if(head.next==slow){
                return true;
            }
                head=head.next;
                slow=slow.next;


        }
        return true;
    }

//    //尾插法
//    public void addLast(int data);
//    //任意位置插入,第一个数据节点为0号下标
//    public boolean addIndex(int index,int data);
//    //查找是否包含关键字key是否在单链表当中
//    public boolean contains(int key);
//    //删除第一次出现关键字为key的节点
//    public void remove(int key);
//    //删除所有值为key的节点
//    public void removeAllKey(int key);
//    //得到单链表的长度
//    public int size();

//    public void clear();
}
